Skip to main content

Assignment 3 Solution

Question 1 Given an array containing 0s and 1s, write an algorithm to sort the array so that all 0s come first followed by 1s​

public static void sortArray(int[] arr) {
  int left = 0;
  int right = arr.length - 1;

  while (left < right) {
    if (arr[left] == 1 && arr[right] == 0) {
      int temp = arr[left];
      arr[left] = arr[right];
      arr[right] = temp;
    }

    if (arr[left] == 0) {
      left++;
    }

    if (arr[right] == 1) {
      right--;
    }
  }
}

Question 2 Given an array containing 0s, 1s, and 2s, write an algorithm to sort the array so that all 0s come first followed by 1s and then 2s​

public static void sort012(int arr[], int n) {
  int low = 0, mid = 0, high = n - 1;
  while (mid <= high) {
    if (arr[mid] == 0) {
      int temp = arr[low];
      arr[low] = arr[mid];
      arr[mid] = temp;
      low++;
      mid++;
    } else if (arr[mid] == 1) {
      mid++;
    } else {
      int temp = arr[mid];
      arr[mid] = arr[high];
      arr[high] = temp;
      high--;
    }
  }
}

Question 4 Find the minimum number of swaps required to bring all elements less than a given value together at the start of the array​

public static int minSwaps(int[] arr, int val) {
  int count = 0;
  for (int i = 0; i < arr.length; i++) {
    if (arr[i] < val) {
      count++;
    }
  }

  int left = 0;
  int right = count - 1;
  int swaps = 0;
  while (left < right) {
    if (arr[left] >= val && arr[right] < val) {
      int temp = arr[left];
      arr[left] = arr[right];
      arr[right] = temp;
      swaps++;
      left++;
      right--;
    } else if (arr[left] < val) {
      left++;
    } else if (arr[right] >= val) {
      right--;
    }
  }

  return swaps;
}

Question 5 [isn't clear] Given two array, sort first array according to the order defined in second array​

Question 6 Separate even numbers from the odd numbers. This method takes an array of integers and moves all even numbers to the left side of the array and all odd numbers to the right side of the array​

public static void separateEvenOdd(int[] arr) {
  int left = 0;
  int right = arr.length - 1;

  while (left < right) {
    if (arr[left] % 2 == 0) {
      left++;
    } else if (arr[right] % 2 != 0) {
      right--;
    } else {
      int temp = arr[left];
      arr[left] = arr[right];
      arr[right] = temp;
      left++;
      right--;
    }
  }

  System.out.println(Arrays.toString(arr));
}

Question 7 Given an array of positive elements, perform a sequence of reduction operations where the smallest positive element is subtracted from all elements until no positive values remain. Print the number of elements remaining after each reduction operation​

public static void reductionProcess(int[] arr) {
  while (arr.length > 0) {
    int minValue = arr[0];
    for (int i = 1; i < arr.length; i++) {
      minValue = Math.min(minValue, arr[i]);
    }
    for (int i = 0; i < arr.length; i++) {
      arr[i] -= minValue;
    }
    int count = 0;
    for (int i : arr) {
      if (i != 0) {
        count++;
      }
    }
    int[] newArray = new int[count];
    int index = 0;
    for (int i : arr) {
      if (i != 0) {
        newArray[index++] = i;
      }
    }
    arr = newArray;
    System.out.println(Arrays.toString(arr));
    System.out.println("length of array: " + arr.length);
  }
}

Question 8 Given two sorted arrays. Sort the elements of these arrays so that first half of sorted elements will lie in first array and second half lies in second array​

(Question Simplified): How to sort two sorted arrays with O(1) extra space such that the first half of the sorted elements lie in the first array and the second half lies in the second array?

public static void sortArrays(int[] arr1, int[] arr2) {
  int n = arr1.length;
  int m = arr2.length;
  int mid = (n + m) / 2;
  if ((n + m) % 2 == 1) {
    mid += 1; 
  }
  int i = 0;
  int j = 0;
  while (i < mid && j < m) {
    if (arr1[i] > arr2[j]) {
      int temp = arr1[i];
      arr1[i] = arr2[j];
      arr2[j] = temp;
      i++; 
    } else {
      i++; 
    }
  }
  Arrays.sort(arr1, mid, n);
  Arrays.sort(arr2, 0, m);
}

Question 9 Given two unsorted arrays, find union and intersection of these two​

public static void findUnionAndIntersection(int[] arr1, int[] arr2) {

  HashSet<Integer> set1 = new HashSet<>();
  HashSet<Integer> set2 = new HashSet<>();

  for (int i : arr1) {
    set1.add(i);
  }

  for (int i : arr2) {
    set2.add(i);
  }

  System.out.println("original Set1: " + set1);
  System.out.println("original Set2: " + set2);

  set1.retainAll(set2);
  System.out.println("Intersection of given arrays: " + set1);

  set1.addAll(set2);
  System.out.println("Union of given arrays: " + set1);
}

Question 10 [question seems unclear/incomplete] In given integer list that support three functions findMin, findMax, find-Median. Sort the array. arrays​

public class ArrayOperations {

  public static double findMedian(int[] a, int n) {
    Arrays.sort(a);
    if (n % 2 != 0) {
      return (double) a[n / 2];
    }
    return (double) (a[(n - 1) / 2] + a[n / 2]) / 2;
  }

  public static int findMax(int[] a, int n) {
    int m = a[0];
    for (int i = 0; i < n; i++) {
      m = Math.max(m, a[i]);
    }
    return m;
  }

  public static int findMin(int[] a, int n) {
    int m = a[0];
    for (int i = 0; i < n; i++) {
      m = Math.min(m, a[i]);
    }
    return m;
  }
}